package LinkList;
public class Exercise {
    //1.关于快慢指针的一个原理是:当他们同时出发且路程相同时，因为快指针是慢指针速度的两倍，所以当快指针到终点时，那么慢指针就是在中间位置
    //2.关于寻找倒数第k个结点的问题，使用快慢指针的原理是:当快指针走到null，慢指针会和快指针相差k步,而这时的慢指针就是倒数第k个结点
    //3.创建一个新空间存放链表是个更好的选择
    //4.链表的头插法要记牢
    //5.链表的回文结构:可以先找中间结点，再从这个结点逆置，然后从头开始比较这个位置之后的值是否相等，相等就是回文链表（其实就是最后一个节点的值与前面得结点的值比较，如果相等就是）
    //6.找公共结点结点就是判断两个链表是否有地址相同的结点，可以直接遍历，也可以让他们的长度相同后，一起走看看有没有交点(当两个结点都走完还没相遇就没有交点  )
    //7.如果要变动已经链接好的结点，那么就需要判断在其他位置插入或者删除已经存在的结点时，有些结点是否还指向别的地方，如果不处理这个问题那么就会造成环形链表的问题，打印时就会死循环

    //8.环形链表:(如果是奇数个结点,那么fast.next==null就说明没有环.如果是偶数个结点，那么fast==null就说明没有环!!!)fast!=null要写在前面不然fast为空了,那么fast.next空指针异常
    //延伸问题(1.为什么fast和slow一定会在环中相遇？会不会在环里面错过，永远遇不上？请证明一下 结论:他们一定会相遇
    //       2.为什么slow走一步fast走两步呢？能不能fast一次走三步四步五步或者说n步呢？请证明一下 结论:fast一次走n步 n>2不一定会相遇)
    //1.分析过程:第一步:slow和fast，一定是fast先进环，这时slow走了入环前距离的一半
    //第二步:随着slow进环，fast已经在环里走了一段距离了，走了多少跟环的大小有关系
    //假设slow进环的时候，slow和fast的距离是n，fast开始追slow
    //slow每次往前走一步，fast往前走两步，每追一次，判断一下相遇
    //每追一次slow和fast的距离变化:n n-1 n-2 ....0每追一次距离减少1，他们之间的距离最后减到0的时候就是相遇的点
    //2.分析过程:假设slow一次走一步，fast一次走三步
    //假设slow进环以后fast和slow距离为n，fast开始追slow
    //他们之间的距离变化为:n n-2  n-4  n-6.....  0/-1      如果n是偶数能追上，是奇数就追不上
    //距离变为-1意味着他们的距离是c-1（c是环的长度）
    //如果这时c-1为奇数，永远追不上          c-1为偶数，能追上

    //追上相遇的过程中：慢指针走的距离:L+X（L=C-Y是slow刚入环到相遇走的长度）    快指针走的距离:L+N*C+X(N是他们相遇之前，fast走的圈数（N>=1）)
    //2(L+X)=L+N*c+x(因为他们的速度差2倍)   假设走了一圈fast就能追上slow，则slow:L+X fast:L+X+C ,则:2(L+X)=L+X+C 即L+X=C;C-Y+X=C  所以X=Y(y是slow走完一圈的长度)
    //L=N*C-X    L=(N-1)*C+C-X; -》（N-1）C=X-Y;


    public static void main(String[] args) {
        LinkList implement=new LinkList();
        implement.addLast(1);
        implement.addLast(4);
        implement.addLast(3);
        implement.addLast(2);
        implement.addLast(5);
        implement.addLast(2);
        //分隔链表:使得小于x的结点存放在大于等于x结点位置之前（提示:创建2个头结点，然后链接）
        ListNode node=partition(implement.getIndex(0),6);
        implement.display(node);
        //给你链表的头节点head和一个整数k,交换链表正数第k个节点和倒数第k个节点的值后返回链表的头节点,链表从1开始索引
        ListNode newnode=swapNodes(implement.getIndex(0),3);
        implement.display(newnode);

        LinkList implement2=new LinkList();
        implement2.addLast(1);
        implement2.addLast(5);
        implement2.addLast(7);
        implement2.addLast(3);
        implement2.head.next=implement.head.next.next;
        ListNode node1=getIntersectionNode(implement.head,implement2.head);
        System.out.println(node1.data);
        implement2.display(implement2.getIndex(0));
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA=0;
        int lenB=0;
        ListNode lA=headA;
        ListNode lB=headB;
        while(lA!=null) {
            lenA++;
            lA=lA.next;
        }
        while(lB!=null) {
            lenB++;
            lB=lB.next;
        }
        lA=headA;
        lB=headB;
        int len=lenA-lenB;

        if(len<0) {
            lA=headB;      //保证lA是最长链表的引用
            lB=headA;
            len=lenB-lenA;
        }
        while((len--)!=0) {
            lA=lA.next;
        }
        while (lA!=lB) {
            lA=lA.next;
            lB=lB.next;
        }
        return lA;
    }
    public static ListNode partition(ListNode head, int x) {
        ListNode Shead=new ListNode(0);
        ListNode Stail=Shead;
        ListNode Lhead=new ListNode(0);
        ListNode Ltail=Lhead;
        ListNode cur=head;
        while(cur!=null) {
            if(cur.data<x) {
                Stail.next=cur;
                Stail=cur;
            }else {
                Ltail.next=cur;
                Ltail=cur;
            }
            cur=cur.next;
        }
        //有可能不会同时存在小于x和大于等于x的结点
        if(Shead.next==null) {   //没有小于x的数
            return Lhead.next;
            //可以直接写成return head;
        }
        if(Lhead.next==null) {        //没有大于x的数
            return Shead.next;
        }
        Ltail.next=null;
        Stail.next=Lhead.next;
        return Shead.next;
    }




    public static ListNode swapNodes(ListNode head, int k) {
        if(k<=0) {
            return null;
        }
        ListNode cur=head;
        ListNode curprev=null;
        ListNode slow=head;
        ListNode slowprev=null;
        ListNode fast=head;
        //目的:找到正数第k个和倒数第k个
        while((k--)-1!=0) {
            fast=fast.next;
            if(fast==null) {
                return null;
            }
            curprev=cur;      //找到cur前一个结点
            cur=cur.next;     //cur走k-1步刚好到正数k的位置
        }
        while(fast.next!=null) {
            slowprev=slow;
            fast=fast.next;
            slow=slow.next;
        }                    //slow就是倒数第k的位置





        ListNode curnext=cur.next;
        ListNode slownext=slow.next;

        ////如果要交换的是相邻的两个结点
        if(cur.next==slow) {
            if(curprev==null) {    //如果这两个结点相邻并且是头尾节点的情况
                slow.next=cur;
                cur.next=null;
                return slow;
            }
            curprev.next=slow;
            slow.next=cur;
            slowprev.next=null;
            cur.next=slownext;
            return head;
        }
        //这里表示k的值大于链表长度一半是会导致，slow在cur的左边
        if(slow.next==cur) {
            if(slowprev==null) {    //如果这两个结点相邻并且是头尾节点的情况
                cur.next=slow;
                slow.next=null;
                return cur;
            }
            slowprev.next=cur;
            cur.next=slow;
            curprev.next=null;
            slow.next=curnext;
            return head;
        }



        //如果slow没有动，而cur已经走到最后(因为根据上面的逻辑是:cur和fast根据k的值走，如果k等于这个链表的长度那么就会造成这个问题)
        if(slow==head&&slownext!=null) {
            curprev.next=curnext;
            cur.next=slownext;
            curprev.next=slow;
            slow.next=null;
            return cur;
        }


        //如果只有一个结点
        if(slowprev==null) {
            return head;
        }


        slowprev.next=slownext;
        //slow在cur右边是执行的逻辑
        if(curprev==null) {   //表示要交换的是头和尾结点
            slow.next=curnext;
            slowprev.next=head;
            head.next=null;
            return slow;
        }

        //正常逻辑
        curprev.next=curnext;
        curprev.next=slow;
        slow.next=curnext;
        slowprev.next=cur;
        cur.next=slownext;
        return head;
    }

    public static ListNode detectCycle(ListNode head) {
        if(head==null) {
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast) {
                ListNode meet=slow;    //在有环的基础上，从起始点和相遇点开始各自一步走，如果相遇就表示这是第一次相遇的点（入口点）
                while(meet!=head) {
                    meet=meet.next;
                    head=head.next;
                }
                return meet;
            }
        }
        return null;
    }
}
